package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [926. 将字符串翻转到单调递增 - 力扣（LeetCode）](https://leetcode.cn/problems/flip-string-to-monotone-increasing/submissions/)
 * @since Created by work on 2022/6/11 21:18
 */
public class FlipStringToMonotoneIncreasing {

    /**
     * 动态规划，状态转移方程：
     * s[i] == '0'
     *  dp[i][0] = dp[i-1][0]
     *  dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + 1(把第i个字符转为1)
     *
     * s[i] == '1'
     *  dp[i][0] = dp[i-1][0] + 1(把第i个字符转为0)
     *  dp[i][1] = min(dp[i-1][0],dp[i-1][1])
     *
     * @param s
     * @return
     */
    public int minFlipsMonoIncr(String s) {
        int len = s.length();
        if (len < 2) {
            return 0;
        }

        /**
         * dp[i][j] 表示前i个字符串满足最长递增子序列，且第i个字符为j的最小转换次数
         */
        int[][] dp = new int[len][2];
        dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
        dp[0][1] = s.charAt(0) == '0' ? 1 : 0;

        for (int i = 1; i < len; i++) {
            if (s.charAt(i) == '0') {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1]) + 1;
            } else {
                dp[i][0] = dp[i-1][0] + 1;
                dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1]);
            }
        }

        return Math.min(dp[len-1][0], dp[len-1][1]);
    }


    /**
     * 动态规划空间优化
     * @param s
     * @return
     */
    public int minFlipsMonoIncr2(String s) {
        int len = s.length();
        if (len < 2) {
            return 0;
        }

        int zero, one;
        zero = s.charAt(0) == '0' ? 0 : 1;
        one = s.charAt(0) == '0' ? 1 : 0;

        for (int i = 1; i < len; i++) {
            /**
             * zero 表示前i-1个字符串满足最长递增子序列，且第i-1个字符为0的最小转换次数
             * one 表示前i-1个字符串满足最长递增子序列，且第i-1个字符为1的最小转换次数
             */
            if (s.charAt(i) == '0') {
                one = Math.min(zero, one) + 1;
            } else {
                /**
                 * 一定要先处理 one， 再处理 zero; 因为zero先处理的话会影响one的结果
                 * 计算本次one、zero的结果，使用的都是上一次one、zero的结果
                 */
                one = Math.min(zero, one);
                zero = zero + 1;
            }
        }

        return Math.min(zero, one);
    }
}

